package com.xie.leetcode.characterstring;

//最长公共前缀
//        编写一个函数来查找字符串数组中的最长公共前缀。
//
//        如果不存在公共前缀，返回空字符串 ""。
//
//         
//
//        示例 1：
//
//        输入：strs = ["flower","flow","flight"]
//        输出："fl"
//        示例 2：
//
//        输入：strs = ["dog","racecar","car"]
//        输出：""
//        解释：输入不存在公共前缀。
//         
//
//        提示：
//
//        1 <= strs.length <= 200
//        0 <= strs[i].length <= 200
//        strs[i] 仅由小写英文字母组成
//        相关标签
//        字符串
//
//        作者：力扣 (LeetCode)
//        链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnmav1/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * @author xiezhendong
 * @date 2021/10/23
 */
public class LongestCommonPrefix {

    public static void main(String[] args) {
        LongestCommonPrefix longestCommonPrefix = new LongestCommonPrefix();
        System.out.println(longestCommonPrefix.longestCommonPrefix(new String[]{"flower", "flow", "flight"}));
        System.out.println(longestCommonPrefix.longestCommonPrefix(new String[]{"dog", "racecar", "car"}));
        System.out.println(longestCommonPrefix.longestCommonPrefix(new String[]{"a"}));
        System.out.println(longestCommonPrefix.longestCommonPrefix(new String[]{"flower", "flower", "flower", "flower"}));
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }

        String sStr = strs[0];
        char[] sChars = sStr.toCharArray();
        String tStr = "";
        for (int i = 0; i < sChars.length; i++) {
            StringBuilder v = new StringBuilder();
            for (int j = 0; j <= i; j++) {
                v.append(sChars[j]);
            }

            int count = 0;
            for (int i1 = 1; i1 < strs.length; i1++) {
                String s = strs[i1];
                char[] scs = s.toCharArray();
                if (scs.length < v.length()) {
                    continue;
                }
                StringBuilder vs = new StringBuilder();
                for (int x = 0; x <= i; x++) {
                    vs.append(scs[x]);
                }
                if (v.toString().equals(vs.toString())) {
                    count++;
                }
            }

            if (count == (strs.length - 1)) {
                tStr = v.toString();
            }

            if (count == 0) {
                break;
            }
        }

        return tStr;
    }
}
